package com.yangzhe.algorithm.c013;

/**
 * https://leetcode.cn/problems/design-circular-queue/
 */
public class QueueStackAndCircularQueue {
    public static void main(String[] args) {
        System.out.println("Test MyQueue:");
        MyQueue myQueue = new MyQueue(3);
        System.out.println("enQueue:" + myQueue.enQueue(1));
        System.out.println("enQueue:" + myQueue.enQueue(2));
        System.out.println("deQueue:" + myQueue.deQueue());
        System.out.println("enQueue:" + myQueue.enQueue(3));
        System.out.println("enQueue:" + myQueue.enQueue(4));
        System.out.println("deQueue:" + myQueue.deQueue());
        System.out.println("deQueue:" + myQueue.deQueue());
        System.out.println("deQueue:" + myQueue.deQueue());

        System.out.println("Test MyCircularQueue:");
        MyCircularQueue obj = new MyCircularQueue(1);
        System.out.println("enQueue:" + obj.enQueue(10));
        System.out.println("deQueue:" + obj.deQueue());
        System.out.println("Front:" + obj.Front());
        System.out.println("Rear:" + obj.Rear());
        System.out.println("isEmpty:" + obj.isEmpty());
        System.out.println("isFull:" + obj.isFull());

    }

    /**
     * 普通队列，入队次数固定
     */
    static class MyQueue {
        public int[] queue;
        public int l = 0;
        public int r = 0;

        public MyQueue(int size) {
            this.queue = new int[size];
        }

        public boolean enQueue(int value) {
            if (r < queue.length) {
                queue[r++] = value;
                return true;
            } else {
                return false;
            }
        }

        public int deQueue() {
            if (l == r) {
                return -1;
            }
            return queue[l++];
        }

        public boolean isEmpty() {
            return l == r;
        }

        public boolean isFull() {
            return r == queue.length - 1;
        }

    }

    /**
     * 循环数组队列，长度固定，入队列次数不固定
     * 队列从尾部进入，从头部出
     */
    static class MyCircularQueue {
        /**
         * 当前队列长度
         */
        public int size;
        /**
         * 最大队列长度
         */
        public int k;
        /**
         * 队列
         */
        public int[] queue;
        /**
         * 队列头
         */
        int l = 0;
        /**
         * 队列尾部+1位置
         */
        int r = 0;

        /**
         * 初始化
         *
         * @param k 队列长度
         */
        public MyCircularQueue(int k) {
            this.k = k;
            queue = new int[k];
        }

        /**
         * 向循环队列插入一个元素。如果成功插入则返回真
         *
         * @param value
         * @return
         */
        public boolean enQueue(int value) {
            if (!isFull()) {
                // 还有位置则加入
                queue[r++] = value;
                size++;
                // 如果r + 1之后溢出数组，则从0开始
                if (r == k) {
                    r = 0;
                }
                return true;
            } else {
                return false;
            }
        }

        /**
         * 从循环队列中删除一个元素。如果成功删除则返回真
         *
         * @return
         */
        public boolean deQueue() {
            if (!isEmpty()) {
                l++;
                size--;
                if (l == k) {
                    l = 0;
                }
                return true;
            } else {
                return false;
            }
        }

        /**
         * 从队首获取元素。如果队列为空，返回 -1
         *
         * @return
         */
        public int Front() {
            if (isEmpty()) {
                return -1;
            } else {
                return queue[l];
            }
        }

        /**
         * 获取队尾元素。如果队列为空，返回 -1
         *
         * @return
         */
        public int Rear() {
            if (isEmpty()) {
                return -1;
            } else {
                // 由于r是队列尾部+1位置，所以返回r-1。
                // 需要判断循环到0的时候，是队列最后一位
                return queue[r == 0 ? k - 1 : r - 1];
            }
        }

        /**
         * 检查循环队列是否为空
         *
         * @return
         */
        public boolean isEmpty() {
            return size == 0;
        }

        /**
         * 检查循环队列是否已满
         *
         * @return
         */
        public boolean isFull() {
            return size == k;
        }
    }


}
